import { getPackedSettings } from "http2";

/**
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 * 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * @param root
 * @returns
 */
const isValidBST = (root: TreeNode | null): boolean => {
    if (root === null) return true

    const stack: TreeNode[] = []

    let prev = -Infinity
    while (stack.length !== 0 || root !== null) {
        while (root !== null) {
            stack.push(root)
            root = root.left;
        }

        // root为空, 此时栈的第一个就是最左边的孩子节点
        const n = stack.pop()!

        // 小于之前的值, 直接返回false
        if (n.val < prev) return false

        prev = n.val;

        root = n.right;
    }
    return true;


};

const isValidBST2 = (root: TreeNode | null): boolean => {
  /**
   * 前序遍历递归
   * @param root
   * @param lower
   * @param upper
   * @returns
   */
  const preOrder = (
    root: TreeNode | null,
    lower: number,
    upper: number
  ): boolean => {
    if (root === null) return true;

    // 如果小于等于了比较小的值 或者 大于等于了比较大的值, 返回false
    if (root.val <= lower || root.val >= upper) return false;

    return (
      preOrder(root.left, lower, root.val) &&
      preOrder(root.right, root.val, upper)
    );
  };

  return preOrder(root, -Infinity, Infinity);
};
